package arrAndstr;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
    54. 螺旋矩阵
 */
public class T54 {

    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
        };
        System.out.println(spiralOrder(matrix));
    }

    public static List<Integer> spiralOrder(int[][] matrix) {
        int row = matrix.length;
        int column = matrix[0].length;
        int sum = row*column;
        List<Integer> result = new ArrayList<>();
        Set<String> set = new HashSet<>();

        int step = 0;
        int forwoard = 0;   // 0%4 --> 0右 1下 2左 3右
        int rowIndex = 0;
        int columnIndex = 0;
        while (step < sum) {
            step++;
            result.add(matrix[rowIndex][columnIndex]);
            set.add(getIndexStr(rowIndex, columnIndex));

            int nextRowIndex = rowIndex;
            int nextColumnIndex = columnIndex;
            if (forwoard==0) {    // 右
                if (columnIndex+1 >= column || set.contains(getIndexStr(rowIndex,columnIndex+1))) {
                    // 该向下了
                    forwoard = 1;
                    rowIndex++;
                } else {
                    columnIndex++;
                }
            } else if (forwoard==1) { // 下
                if (rowIndex+1 >= row || set.contains(getIndexStr(rowIndex+1, columnIndex))) {
                    // 该向左了
                    forwoard = 2;
                    columnIndex--;
                } else {
                    rowIndex++;
                }
            } else if (forwoard==2) { // 左
                if (columnIndex-1 < 0 || set.contains(getIndexStr(rowIndex, columnIndex-1))) {
                    // 该向上了
                    forwoard = 3;
                    rowIndex--;
                } else {
                    columnIndex--;
                }
            } else {    // 上
                if (rowIndex-1 < 0 || set.contains(getIndexStr(rowIndex-1, columnIndex))) {
                    // 该向右了
                    forwoard = 0;
                    columnIndex++;
                } else {
                    rowIndex--;
                }
            }
        }

        return result;
    }

    public static String getIndexStr(int i, int j) {
        return String.valueOf(i) + "-" + String.valueOf(j);
    }
}
